package main

import "fmt"

type Node struct {
	value int
	next  *Node
}

//func addTwoNumbers(n1, n2 *Node) *Node {
//	resultNode := &Node{}
//	tmpNode := resultNode
//
//	sum := 0
//
//	for n1 != nil || n2 != nil || sum != 0 {
//		if n1 != nil {
//			sum += n1.value
//			n1 = n1.next
//		}
//
//		if n2 != nil {
//			sum += n2.value
//			n2 = n2.next
//		}
//
//		tmpNode.next = &Node{sum % 10, nil}
//		tmpNode = tmpNode.next
//		sum /= 10
//	}
//
//	return resultNode.next
//}

func addTwoNumbers(n1, n2 *Node) *Node {
	pre := new(Node)
	pre.value = 0
	cur := pre
	carry := 0
	for n1 != nil || n2 != nil {
		var (
			x = 0
			y = 0
		)
		if n1 != nil {
			x = n1.value
		}

		if n2 != nil {
			y = n2.value
		}

		sum := x + y + carry

		carry = sum / 10
		sum = sum % 10

		newNode := new(Node)
		newNode.value = sum
		cur.next = newNode
		cur = cur.next

		if n1 != nil {
			n1 = n1.next
		}

		if n2 != nil {
			n2 = n2.next
		}
	}

	// 最高位是进位得来的
	// 那么就直接新建一个节点
	if carry == 1 {
		newNode := new(Node)
		newNode.value = carry
		cur.next = newNode
	}
	// 因为第一位是0 所以需要放弃
	return pre.next
}

func addNumbers2(n1, n2 *Node) *Node {
	ret := new(Node)
	cur := ret
	add := 0
	for n1 != nil || n2 != nil || add > 0 {
		val1, val2 := 0, 0
		if n1 != nil {
			val1, n1 = n1.value, n1.next
		}
		if n2 != nil {
			val2, n2 = n2.value, n2.next
		}
		val := val1 + val2 + add
		add = val / 10
		cur.next = &Node{
			value: val % 10,
			next:  nil,
		}
		cur = cur.next
	}
	return ret.next
}

func main() {

	n1 := &Node{
		value: 5,
	}
	n11 := &Node{
		value: 4,
	}
	n111 := &Node{
		value: 3,
	}
	n1.next = n11
	n11.next = n111

	n2 := &Node{
		value: 5,
	}
	n22 := &Node{
		value: 6,
	}
	n222 := &Node{
		value: 4,
	}
	n2.next = n22
	n22.next = n222

	//r := addTwoNumbers(n1, n2)
	r := addNumbers2(n1, n2)
	fmt.Println(r)
}
